#include "stack.h"
#include "stdio.h"
#include "string.h"
#include "stdlib.h"


extern int top;
extern NODE* STACK[];

void initializeTree();
void MakeTree();
void traverse(NODE *node);
void visit(NODE *node);
void recursive_Traverse(NODE *node);
void traverse_middle(NODE *node);

NODE *parent, *leftChild, *rightChild;
NODE *headNode, *endNode;

int main (int argc, char *argv[])
{
	initializeTree();
	MakeTree();
	//traverse(headNode->left);
	//recursive_Traverse(headNode->left);

	traverse_middle(headNode->left);

	return EXIT_SUCCESS;
}

void initializeTree()
{
	headNode = (NODE*)malloc(sizeof(NODE));
	NODEfuncInit(headNode);
	headNode->init(headNode, "head");

	endNode = (NODE*)malloc(sizeof(NODE));
	NODEfuncInit(endNode);
	endNode->init(endNode, "end");

	headNode->left = endNode;
	headNode->right = endNode;

	endNode->left = headNode;
	endNode->right = headNode;
}


void MakeTree()
{
	////////////////////
	parent = (NODE*)malloc(sizeof(NODE));
	NODEfuncInit(parent);
	parent->init(parent, "A");

	leftChild = (NODE*)malloc(sizeof(NODE));
	NODEfuncInit(leftChild);
	leftChild->init(leftChild, "B");

	rightChild = (NODE*)malloc(sizeof(NODE));
	NODEfuncInit(rightChild);
	rightChild->init(rightChild, "C");

	headNode->left = parent;
	headNode->right = parent;
	parent->left = leftChild;
	parent->right = rightChild;
	////////////////////////
	
	//////////////////////
	parent = parent->left;

	leftChild = (NODE*)malloc(sizeof(NODE));
	NODEfuncInit(leftChild);
	leftChild->init(leftChild, "D");
	leftChild->right = endNode;
	leftChild->left = endNode;

	rightChild = (NODE*)malloc(sizeof(NODE));
	NODEfuncInit(rightChild);
	rightChild->init(rightChild, "E");
	rightChild->left = endNode;
	rightChild->right = endNode;

	parent->left = leftChild;
	parent->right = rightChild;
	///////////////////////////

	/////////////////////////
	parent = headNode->right->right;

	leftChild = (NODE*)malloc(sizeof(NODE));
	NODEfuncInit(leftChild);
	leftChild->init(leftChild, "F");
	leftChild->left = endNode;
	leftChild->right = endNode;

	rightChild = (NODE*)malloc(sizeof(NODE));
	NODEfuncInit(rightChild);
	rightChild->init(rightChild, "G");
	rightChild->left = endNode;
	rightChild->right = endNode;

	parent->left = leftChild;
	parent->right = rightChild;
	//////////////////////////
}

// void traverse(NODE *node)
// {
// 	push(node);
// 	while(!isStackEmpty())
// 	{
// 		node = pop();
// 		visit(node);
// 		if(node->right != endNode)
// 			push(node->right);
// 		if(node->left != endNode)
// 			push(node->left);
// 	}
// }

void visit(NODE *node)
{
	printf("%s ->", node->data);
}

// void recursive_Traverse(NODE *node)
// {
// 	if(node != endNode) {
// 		recursive_Traverse(node->left);
// 		visit(node);
// 		recursive_Traverse(node->right);
// 
// 	}
// }

// void traverse_middle(NODE *node)
// {
// 	int finish = false;
// 	do {
// 		while(node != endNode) {
// 			push(node);
// 			node = node->left;
// 		}
// 		if (!isStackEmpty())
// 		{
// 			node = pop();
// 			visit(node);
// 			node = node->right;
// 		}
// 		else
// 			finish = 1;
// 	} while(!finish);
// 	
// }
// 
// void recursive_Traverse(NODE *node)
// {
// 	if(node != endNode) {
// 		recursive_Traverse(node->left);
// 		recursive_Traverse(node->right);
// 		visit(node);
// 	}
// }

void traverse_middle(NODE *node)
{
	bool finish = false;
	while (!finish)
	{
		while(node != endNode) 
		{
			push(node);
			node = node->left;
		}
		if(!isStackEmpty()) {
			node = pop();
			visit(node);
			node = node->right;
		}else
			finish = true;
	}
}

void traverse(NODE *node)
{
	push(node);

	while(!isStackEmpty())
	{
		node = pop();
		visit(node);
		if (node->right != endNode)
			push(node->right);
		if(node->left != endNode)
			push(node->left);			
	}
}

void row_traverse(NODE *node)
{


}